{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Good Numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #recursion #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #递归 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countGoodNumbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计好数字的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>我们称一个数字字符串是 <strong>好数字</strong> 当它满足（下标从 <strong>0</strong> 开始）<strong>偶数</strong> 下标处的数字为 <strong>偶数</strong> 且 <strong>奇数</strong> 下标处的数字为 <strong>质数</strong> （<code>2</code>，<code>3</code>，<code>5</code> 或 <code>7</code>）。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，<code>\"2582\"</code> 是好数字，因为偶数下标处的数字（<code>2</code> 和 <code>8</code>）是偶数且奇数下标处的数字（<code>5</code> 和 <code>2</code>）为质数。但 <code>\"3245\"</code> <strong>不是</strong> 好数字，因为 <code>3</code> 在偶数下标处但不是偶数。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个整数 <code>n</code> ，请你返回长度为 <code>n</code> 且为好数字的数字字符串 <strong>总数</strong> 。由于答案可能会很大，请你将它对<strong> </strong><code>10<sup>9</sup> + 7</code> <strong>取余后返回</strong> 。</p>\n",
    "\n",
    "<p>一个 <strong>数字字符串</strong> 是每一位都由 <code>0</code> 到 <code>9</code> 组成的字符串，且可能包含前导 0 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 1\n",
    "<b>输出：</b>5\n",
    "<b>解释：</b>长度为 1 的好数字包括 \"0\"，\"2\"，\"4\"，\"6\"，\"8\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 4\n",
    "<b>输出：</b>400\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 50\n",
    "<b>输出：</b>564908303\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= n <= 10<sup>15</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-good-numbers](https://leetcode.cn/problems/count-good-numbers/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-good-numbers](https://leetcode.cn/problems/count-good-numbers/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1', '4', '50']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        m = 1000000007\n",
    "        return pow(5, n+1>>1, m) * pow(4, n>>1, m) % m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "\n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        a = pow(5, (n + 1) // 2, MOD)\n",
    "\n",
    "        b = pow(4, n // 2, MOD)\n",
    "\n",
    "        return (a * b) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        return pow(20, n>>1, 10**9+7) * (n&1 and 5 or 1) % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        mod = 10**9 +7\n",
    "        ans = pow(20, n//2, mod)\n",
    "        if n%2:\n",
    "            ans = ans * 5 % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        mod = 7 + 10 ** 9\n",
    "\n",
    "        def quickmul(x: int, y: int) -> int:\n",
    "            ret, mul = 1, x\n",
    "            while y > 0:\n",
    "                if y % 2 == 1:\n",
    "                    ret = ret * mul % mod\n",
    "                mul = mul * mul % mod\n",
    "                y //= 2\n",
    "            return ret\n",
    "\n",
    "        \n",
    "        return quickmul(5, (n + 1) // 2) * quickmul(4, n // 2) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        result = pow(20, n>>1, 10**9+7)\n",
    "        return result * 5 % (10**9+7) if n & 1 else result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        k = n // 2\n",
    "        ans = 1\n",
    "        mul = 20\n",
    "        while k > 0:\n",
    "            if k % 2 == 1:\n",
    "                ans = ans * mul % mod\n",
    "            mul = mul * mul % mod\n",
    "            k //= 2\n",
    "        if n % 2 == 1:\n",
    "            ans = ans * 5 % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        return int(pow(5, (n + 1) // 2, 1000000007) * pow(4, n // 2, 1000000007) % 1000000007)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        def pow(x:int,y:int)->int:\n",
    "            res = 1\n",
    "            mul = x\n",
    "            while y>0:\n",
    "                if y%2==1:\n",
    "                    res = res*mul%mod\n",
    "                mul = mul * mul%mod\n",
    "                y//=2\n",
    "            return res\n",
    "        return pow(5,(n+1)//2)*pow(4,n//2)%mod\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        mod=10**9+7\n",
    "        m=n//2\n",
    "\n",
    "        def quickMul(x,n):\n",
    "            ans,mul=1,x\n",
    "            while n>0:\n",
    "                if n%2==1:\n",
    "                    ans=ans*mul%mod\n",
    "                mul*=mul%mod\n",
    "                n//=2\n",
    "            return ans\n",
    "        \n",
    "        ans=quickMul(20,m)\n",
    "        if n%2==1:\n",
    "            ans=ans*5%mod\n",
    "\n",
    "        return ans\n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        a1 = (n + 1) // 2\n",
    "        a2 =  n // 2\n",
    "        return  pow(5, a1, MOD) * pow(4, a2, MOD) % MOD "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        mod=1000000007\n",
    "        premier=[2,3,5,7]\n",
    "\n",
    "        even=math.ceil(n/2)\n",
    "        odd=n-even\n",
    "\n",
    "        even_sum=1\n",
    "        odd_sum=1\n",
    "        def qpow(a,b ,mod):\n",
    "\n",
    "            res=1\n",
    "            while(b):\n",
    "                if(b&1):\n",
    "                    res*=a%mod \n",
    "                a=(a*a)%mod \n",
    "\n",
    "                b>>=1\n",
    "            return res\n",
    "        return qpow(4,odd,mod)*qpow(5,even,mod)%mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        return (pow(5,(n+1)//2,1000000007)*pow(4,n//2,1000000007))%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        p = 10**9 + 7\n",
    "        return pow(4,n//2,p)*pow(5,(n+1)//2,p)%p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        return pow(20, n>>1, 10**9+7) * (1,5)[n&1] % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        mod=10**9+7\n",
    "        m=n//2\n",
    "\n",
    "        def quickMul(x,n):\n",
    "            ans,mul=1,x\n",
    "            while n>0:\n",
    "                if n%2==1:\n",
    "                    ans=ans*mul%mod\n",
    "                mul*=mul%mod\n",
    "                n//=2\n",
    "            return ans\n",
    "        \n",
    "        ans=quickMul(20,m)\n",
    "        if n%2==1:\n",
    "            ans=ans*5%mod\n",
    "\n",
    "        return ans\n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        l=0\n",
    "        r=0\n",
    "        MOD=10**9+7\n",
    "        if n%2:\n",
    "           l=n//2+1\n",
    "           r=n//2\n",
    "        else:\n",
    "           l,r=n//2,n//2\n",
    "\n",
    "        return (pow(5,l,MOD))*(pow(4,r,MOD))%(10**9+7)         \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        return pow(4, n // 2, MOD) * pow(5, (n + 1) // 2, MOD) % MOD\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "\n",
    "        MOD = (10 ** 9 + 7)\n",
    "\n",
    "        def pow(a, n):\n",
    "            result = 1\n",
    "            while n > 0:\n",
    "                if n % 2 == 1:\n",
    "                    result = result * a\n",
    "                a = a * a % MOD\n",
    "                n = n // 2\n",
    "            return result % MOD\n",
    "\n",
    "        return (pow(5, (n + 1) // 2) * pow(4, n // 2)) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        if n < 2:\n",
    "            return 5\n",
    "        t = n // 2\n",
    "        return (pow(5, n - t, MOD) * pow(4, t, MOD)) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        m = 10**9+7\n",
    "        return pow(20, n>>1, m) * (1,5)[n&1] % m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        mod=10**9+7\n",
    "        def quickMul(x,n):\n",
    "            ans,mul=1,x\n",
    "            while n:\n",
    "                if n&1>0:\n",
    "                    ans*=mul%mod\n",
    "                mul*=mul%mod\n",
    "                n>>=1\n",
    "            return ans\n",
    "\n",
    "        return quickMul(5,(n+1)//2)*quickMul(4,n//2)%mod\n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        M = 10**9+7\n",
    "        result = 1\n",
    "        if(n % 2 == 0):\n",
    "            n1, n2 = n//2, n//2\n",
    "        else:\n",
    "            n1, n2 = n//2, n//2+1\n",
    "        # @cache\n",
    "        def quickPower(num, p):\n",
    "            if(p == 0):\n",
    "                return  1\n",
    "            if(p == 1):\n",
    "                return num\n",
    "            cnt = 1\n",
    "            x = num\n",
    "            while(cnt * 2 <= p):\n",
    "                x = x ** 2 % M\n",
    "                cnt *= 2\n",
    "            return x * quickPower(num, p-cnt) % M\n",
    "        return quickPower(4,n1) * quickPower(5,n2) % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        mod = 10**9 +7\n",
    "\n",
    "        def pow(x,y):\n",
    "            if y == 0:\n",
    "                return 1\n",
    "            res = pow(x,y//2)\n",
    "            return (res*res)%mod if y%2 ==0 else (res*res*x)%(mod)\n",
    "           \n",
    "        return (pow(5,(n+1)//2) * pow(4,(n//2))) %(mod)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        a, b = (n + 1) // 2, n // 2\n",
    "        return (pow(5, a, kmod) * pow(4, b, kmod)) % kmod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        \n",
    "        # 快速幂求出 x^y % mod\n",
    "        def quickmul(x: int, y: int) -> int:\n",
    "            ret, mul = 1, x\n",
    "            while y > 0:\n",
    "                if y % 2 == 1:\n",
    "                    ret = ret * mul % mod\n",
    "                mul = mul * mul % mod\n",
    "                y //= 2\n",
    "            return ret\n",
    "            \n",
    "        return quickmul(5, (n + 1) // 2) * quickmul(4, n // 2) % mod\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        mod=10**9+7\n",
    "        def quickMul(x,n):\n",
    "            ans,mul=1,x\n",
    "            while n:\n",
    "                if n&1>0:\n",
    "                    ans=(ans*mul)%mod\n",
    "                mul=(mul*mul)%mod\n",
    "                n>>=1\n",
    "            return ans\n",
    "\n",
    "        return quickMul(5,(n+1)//2)*quickMul(4,n//2)%mod\n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        mod = 10**9 +7\n",
    "\n",
    "        def pow(x,y):\n",
    "            if y == 0:\n",
    "                return 1\n",
    "            res = pow(x,y//2)\n",
    "            return (res*res)%mod if y%2 ==0 else (res*res*x)%(mod)\n",
    "           \n",
    "        return (pow(5,(n+1)//2) * pow(4,(n//2))) %(mod)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        # N = n // 2\n",
    "        # x = 20\n",
    "\n",
    "        # def quickMul(N):\n",
    "        #     if N == 0: return 1\n",
    "        #     y = quickMul(N // 2)\n",
    "        #     return y * y if N % 2 == 0 else y * y * 20\n",
    "\n",
    "        # res = quickMul(N) % (10 ** 9 + 7)\n",
    "        # res = res if n % 2 == 0 else res * 5\n",
    "        # return res\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        def quickMul(x, n):\n",
    "            res = 1\n",
    "            while n:\n",
    "                if n % 2:\n",
    "                    res = res * x % mod\n",
    "                x = x * x % mod\n",
    "                n //= 2\n",
    "            return res\n",
    "        \n",
    "        return quickMul(5, (n+1)//2) * quickMul(4, n//2) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9+7\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        a = n//2\n",
    "        b = a+n%2\n",
    "        return int(pow(4,a,MOD)*pow(5,b,MOD))%MOD "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        return (pow(5,(n+1)//2,10**9+7)*(pow(4,n//2,10**9+7)))%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        # 快速幂求出 x^y % mod\n",
    "        def quickmul(x: int, y: int) -> int:\n",
    "            ret, mul = 1, x\n",
    "            while y > 0:\n",
    "                if y % 2 == 1:\n",
    "                    ret = ret * mul % mod\n",
    "                mul = mul * mul % mod\n",
    "                y //= 2\n",
    "            return ret\n",
    "        return quickmul(5, (n + 1) // 2) * quickmul(4, n // 2) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        mod=10**9+7\n",
    "        def quickMul(x,n):\n",
    "            ans,mul=1,x\n",
    "            while n>0:\n",
    "                if n%2==1:\n",
    "                    ans=ans*mul%mod\n",
    "                mul*=mul%mod\n",
    "                n//=2\n",
    "            return ans\n",
    "\n",
    "        return quickMul(5,(n+1)//2)*quickMul(4,n//2)%mod\n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        M = 10**9+7\n",
    "        result = 1\n",
    "        if(n % 2 == 0):\n",
    "            n1, n2 = n//2, n//2\n",
    "        else:\n",
    "            n1, n2 = n//2, n//2+1\n",
    "        # @cache\n",
    "        def quickPower(num, p):\n",
    "            if(p == 0):\n",
    "                return  1\n",
    "            if(p == 1):\n",
    "                return num\n",
    "            cnt = 1\n",
    "            x = num\n",
    "            while(cnt * 2 <= p):\n",
    "                x = x ** 2 % M\n",
    "                cnt *= 2\n",
    "            return x * quickPower(num, p-cnt) % M\n",
    "        return quickPower(4,n1) * quickPower(5,n2) % M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        mod = 10**9+7\n",
    "\n",
    "        def quick(x,y):\n",
    "            if y == 0:\n",
    "                return 1\n",
    "            ret = quick(x,y//2)\n",
    "            return ret * ret * x % mod if y % 2 else ret * ret % mod\n",
    "\n",
    "        \n",
    "        return quick(5,(n+1)//2) * quick(4,n//2) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        even = pow(5, (n+1) // 2 , MOD)\n",
    "        odd = pow(4, n // 2 , MOD)\n",
    "        return (even * odd) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 1_000_000_007\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        # 偶数：0, 2, 4, 6, 8，放在偶下标\n",
    "        # 质数：2, 3, 5, 7, 放在奇下标\n",
    "\n",
    "        return (pow(5, n - n // 2, MOD) * pow(4, n // 2, MOD)) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        def f(a, x):\n",
    "            t = 1\n",
    "            while x:\n",
    "                if x % 2 == 1:\n",
    "                    t = t*a\n",
    "                a = a*a % (10**9+7)\n",
    "                x = x >> 1\n",
    "            return t\n",
    "\n",
    "        return f(4, n//2) * f(5, n-(n//2)) % (10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        mod=1000000007\n",
    "        premier=[2,3,5,7]\n",
    "\n",
    "        even=math.ceil(n/2)\n",
    "        odd=n-even\n",
    "\n",
    "        even_sum=1\n",
    "        odd_sum=1\n",
    "       \n",
    "        return pow(4,odd,mod)*pow(5,even,mod)%mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "\n",
    "        def pow(a, n):\n",
    "            result = 1\n",
    "            while n > 0:\n",
    "                if n % 2 == 1:\n",
    "                    result = result * a\n",
    "                a = a * a % (10 ** 9 + 7)\n",
    "                n = n // 2\n",
    "            return result % (10 ** 9 + 7)\n",
    "\n",
    "        return (pow(5, (n + 1) // 2) * pow(4, n // 2)) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    ''' 调用标准库\r\n",
    "    def countGoodNumbers(self, n: int) -> int:\r\n",
    "        MOD = 10 ** 9 + 7\r\n",
    "        a = pow(5, (n + 1) // 2, MOD)\r\n",
    "        b = pow(4, n // 2, MOD)\r\n",
    "        return (a * b) % MOD\r\n",
    "    '''        \r\n",
    "\r\n",
    "    def countGoodNumbers(self, n: int) -> int:\r\n",
    "        MOD = 10 ** 9 + 7\r\n",
    "        def quick_mul(a: int, b: int) -> int:\r\n",
    "            res = 1\r\n",
    "            while b:\r\n",
    "                if b % 2 == 1:\r\n",
    "                    res = res * a % MOD\r\n",
    "                a = a * a % MOD\r\n",
    "                b //= 2\r\n",
    "            return res\r\n",
    "\r\n",
    "        a = quick_mul(5, (n+1)//2)\r\n",
    "        b = quick_mul(4, n // 2)\r\n",
    "        return (a * b) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10 ** 9 + 7\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        # 1 *5*4*5*4……\n",
    "        ans = pow(20, n >> 1, MOD)\n",
    "        return ans * 5 % MOD if n & 1 else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countGoodNumbers(self, n: int) -> int:\n",
    "        M = 10**9+7\n",
    "        result = 1\n",
    "        if(n % 2 == 0):\n",
    "            n1, n2 = n//2, n//2\n",
    "        else:\n",
    "            n1, n2 = n//2, n//2+1\n",
    "        @cache\n",
    "        def quickPower(num, p):\n",
    "            if(p == 0):\n",
    "                return  1\n",
    "            if(p == 1):\n",
    "                return num\n",
    "            cnt = 1\n",
    "            x = num\n",
    "            while(cnt * 2 <= p):\n",
    "                x = x ** 2 % M\n",
    "                cnt *= 2\n",
    "            return x * quickPower(num, p-cnt) % M\n",
    "        return quickPower(4,n1) * quickPower(5,n2) % M"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
